/*
 *    Copyright 2023 The ChampSim Contributors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

/// 一个基于LRU替换策略的缓存表

#ifndef MSL_LRU_TABLE_H
#define MSL_LRU_TABLE_H

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <optional>
#include <stdexcept>
#include <type_traits>
#include <utility>
#include <vector>

#include "extent.h"
#include "msl/bits.h"
#include "util/detect.h"
#include "util/span.h"
#include "util/type_traits.h"

namespace champsim
{
template <typename Extent>
class address_slice;
}

namespace champsim::msl
{
namespace detail /// lru_table 类的基础设施
{
template <typename T>
struct table_indexer { /// 用于从数据 T 中提取组索引（set index）
  auto operator()(const T& t) const { return t.index(); }
};
/// index函数和tag函数都在具体的模板T的实现中被定义, 例如`./btb/basic_btb/direct_predictor.h`中定义了index和tag
template <typename T>
struct table_tagger { /// 用于从数据 T 中提取标签（tag）
  auto operator()(const T& t) const { return t.tag(); }
};
/// 安全比较两个可能具有不同符号性（有符号 / 无符号）的整数类型 T 和 U 是否相等，
// 避免因符号转换导致的意外错误
template <class T, class U>
constexpr bool cmp_equal(T t, U u) noexcept 
{
  using UT = std::make_unsigned_t<T>;
  using UU = std::make_unsigned_t<U>;
  if constexpr (std::is_signed_v<T> == std::is_signed_v<U>)
    return t == u;
  else if constexpr (std::is_signed_v<T>)
    return t < 0 ? false : UT(t) == u;
  else
    return u < 0 ? false : t == UU(u);
}
} // namespace detail
/// T: 缓存中存储的数据类型, 
/// SetProj: 用于从数据T中提取 “组索引” 的投影函数（默认使用T的index()方法）
/// TagProj：用于从数据T中提取 “标签（tag）” 的投影函数（默认使用T的tag()方法）
template <typename T, typename SetProj = detail::table_indexer<T>, typename TagProj = detail::table_tagger<T>>
class lru_table
{
public:
  using value_type = T;

private:
  struct block_t {
    uint64_t last_used = 0;
    value_type data; /// 实际存储的数据, 类型为T
  };
  using block_vec_type = std::vector<block_t>;
  using diff_type = typename block_vec_type::difference_type;
  /// 投影函数实例
  SetProj set_projection; 
  TagProj tag_projection;
  /// 缓存的组数和每组的路数（容量 = 组数 × 路数）
  diff_type NUM_SET; 
  diff_type NUM_WAY;
  /// 全局访问计数器（用于生成last_used时间戳）
  uint64_t access_count = 0;
  /// 存储所有缓存块的向量（按 “组 - 路” 顺序排列）
  block_vec_type block;

  /// ------- 根据Index找Set, Search 逻辑
  /// 获取指定数据所在的组, 
  /// 用于根据输入的数据元素，定位到它在缓存中所属的「组（set）」，并返回该组在内存中的迭代器范围（即该组包含的所有缓存块的起始和结束位置）
  auto get_set_span(const value_type& elem)
  {
    diff_type set_idx;
    /// 获得 diff_type 类型的组索引
    /// 如果投影函数的返回值是 champsim::address_slice 类型（一种表示地址片段的专用类型，常用于缓存索引 / 标签提取），
    /// 则调用其模板方法 to<decltype(set_idx)>() 转换为 diff_type 类型的组索引。
    if constexpr (champsim::is_specialization_v<std::invoke_result_t<SetProj, decltype(elem)>, champsim::address_slice>) {
      set_idx = set_projection(elem).template to<decltype(set_idx)>();
    } else { /// 其他类型（如整数），则直接通过 static_cast 转换为 diff_type 类型的组索引。
      set_idx = static_cast<diff_type>(set_projection(elem));
    }
    if (set_idx < 0)
      throw std::range_error{"Set projection produced negative set index: " + std::to_string(set_idx)};
    /// 计算组在缓存块向量中的起始位置
    diff_type raw_idx{(set_idx % NUM_SET) * NUM_WAY};
    /// 获取组内缓存块的迭代器范围
    auto begin = std::next(std::begin(block), raw_idx); /// 起始迭代器
    auto end = std::next(begin, NUM_WAY); /// 移动到该组最后一个缓存块的下一个位置
    return std::pair{begin, end};
  }
  
  /// ------ 根据Tag判断是否命中, hit逻辑
  /// 判断缓存块（block_t）是否与目标数据元素（elem）匹配
  /// 用于生成一个lambda 表达式（匿名函数），该函数的作用是判断缓存块（block_t）是否与目标数据元素（elem）匹配。
  /// 这个匹配逻辑是缓存命中检查、数据失效等操作的核心依据。
  auto match_func(const value_type& elem)
  {
    /// 这部分定义了一个 lambda 表达式，包含捕获列表和匹配逻辑：
    /// tag = tag_projection(elem): 从 elem 中提取标签（tag）
    /// proj = this->tag_projection: 捕获当前类的 tag_projection 实例（即标签投影函数），用于后续从缓存块中提取标签
    /// 参数 const block_t& x：表示一个待检查的缓存块
    return [tag = tag_projection(elem), proj = this->tag_projection](const block_t& x) {
      /// 条件 1：x.last_used > 0:
      // 缓存块的 last_used 记录了最近访问时间戳（0 表示该块无效，即未存储有效数据）。 
      // 这个条件确保只匹配有效缓存块（排除空块或已失效的块）。
      /// 条件 2：proj(x.data) == tag
      // 使用捕获的标签投影函数 proj 从缓存块 x 的数据（x.data）中提取标签，与目标元素 elem 的标签（tag）比较。 
      // 这个条件确保缓存块存储的数据与目标元素 elem 是同一个数据（标签匹配）。
      return x.last_used > 0 && proj(x.data) == tag;
    };
  }

  /// LRU替换算法, 选择一个Set中被替换的路
  template <typename U>
  auto match_and_check(U tag)
  {
    /// 1. 无效块优先被替换
    /// 2. 若 x 有效，则需进一步判断 y 的情况
    /// 3. 标签不匹配的块优先被替换: (!x_match && y_match) → 如果 x 的标签与目标不匹配，而 y 的标签与目标匹配（y 是命中块），则 x 更适合被替换（返回 true）
    /// 4. 标签匹配状态相同时，按 LRU 规则判断
    return [tag, proj = this->tag_projection](const auto& x, const auto& y) {
      auto x_valid = x.last_used > 0; /// 块是否有效（last_used > 0，无效块优先被替换）
      auto y_valid = y.last_used > 0; 
      auto x_match = proj(x.data) == tag; /// 块的标签是否与目标数据匹配（匹配的块是 “命中”，不应被替换,）；
      auto y_match = proj(y.data) == tag;
      auto cmp_lru = x.last_used < y.last_used; /// LRU 策略：最久未使用的块优先被替换
      return !x_valid || (y_valid && ((!x_match && y_match) || ((x_match == y_match) && cmp_lru)));
    };
  }

public:
  /// 检查数据是否命中缓存
  std::optional<value_type> check_hit(const value_type& elem)
  {
    /// 调用 get_set_span 方法，获取 elem 所属缓存组(Set)的迭代器范围
    auto [set_begin, set_end] = get_set_span(elem);
    /// std::find_if 是 STL 算法，用于在迭代器范围 [set_begin, set_end) 中查找第一个满足条件match_func的元素:
    // 仅当缓存块有效（last_used > 0）且标签与 elem 匹配时，才视为 “命中”,满足match_func。
    auto hit = std::find_if(set_begin, set_end, match_func(elem));

    if (hit == set_end) { /// 未命中
      return std::nullopt;
    }

    hit->last_used = ++access_count;
    return hit->data; /// 命中后更新访问时间并返回数据
  }
  /// 将数据填充到缓存（若满则替换）
  void fill(const value_type& elem)
  {
    auto tag = tag_projection(elem);
    /// 调用get_set_span,返回elem应该插入的组(Set)的迭代
    auto [set_begin, set_end] = get_set_span(elem);
    if (set_begin != set_end) {
      /// 迭代器范围 [first, last) 中，通过match_and_check比较函数
      ///  其中最适合被替换的块是miss, tag和elem一样的块是hit(命中的块)
      auto [miss, hit] = std::minmax_element(set_begin, set_end, match_and_check(tag));

      if (tag_projection(hit->data) == tag) {
        *hit = {++access_count, elem}; /// 如果有命中的块,直接更新这个块
      } else {
        *miss = {++access_count, elem}; /// 如果没有命中的块, 则按照LRU算法替换块
      }
    }
  }

  /// 将目标数据从缓存中 “失效”
  /// 查找缓存中与 elem 匹配的块，若存在则将其置为无效状态，并返回被失效的数据；若不存在则返回空
  std::optional<value_type> invalidate(const value_type& elem)
  {
    auto [set_begin, set_end] = get_set_span(elem);
    auto hit = std::find_if(set_begin, set_end, match_func(elem));

    if (hit == set_end) {
      return std::nullopt;
    }

    return std::exchange(*hit, {}).data;
  }

  lru_table(std::size_t sets, std::size_t ways, SetProj set_proj, TagProj tag_proj)
      : set_projection(set_proj), tag_projection(tag_proj), NUM_SET(static_cast<diff_type>(sets)), NUM_WAY(static_cast<diff_type>(ways)), block(sets * ways)
  {
    if (!detail::cmp_equal(sets, static_cast<diff_type>(sets)))
      throw std::overflow_error{"Sets is out of bounds"};
    if (!detail::cmp_equal(ways, static_cast<diff_type>(ways)))
      throw std::overflow_error{"Ways is out of bounds"};
    if (sets <= 0)
      throw std::range_error{"Sets is not positive"};
    if ((sets & (sets - 1)) != 0)
      throw std::range_error{"Sets is not a power of 2"};
  }

  lru_table(std::size_t sets, std::size_t ways, SetProj set_proj) : lru_table(sets, ways, set_proj, {}) {}
  lru_table(std::size_t sets, std::size_t ways) : lru_table(sets, ways, {}, {}) {}
};
} // namespace champsim::msl

#endif
